package com.zhuang.daily.twofive;


import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * description: Solution001
 * date: 2025/7/15 8:30
 * author: Zhuang
 * version: 1.0
 */
public class Solution01 {

    public static void main(String[] args) {
        Solution01 solution001 = new Solution01();
        solution001.convert("PAYPALISHIRING", 3);
    }

    public static boolean isValid(String word) {
        if (word.length() < 3) {
            return false;
        }
        boolean hasVowel = false;
        boolean hasConsonant = false;
        for (char c : word.toCharArray()) {
            if (Character.isLetter(c)) {
                char ch = Character.toLowerCase(c);
                if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u') {
                    hasVowel = true;
                } else {
                    hasConsonant = true;
                }
            } else if (!Character.isDigit(c)) {
                return false;
            }
        }
        return hasConsonant && hasVowel;
    }

    public static boolean isValid2(String word) {
        if (word.length() < 3) {
            return false;
        }
        int judge = 0;
        Set<Character> vowels = new HashSet<>(Arrays.asList(
                'a', 'e', 'i', 'o', 'u',  // 小写元音
                'A', 'E', 'I', 'O', 'U'   // 大写元音
        ));
        for (char c : word.toCharArray()) {
            if ('0' <= c && c <= '9') continue;
            if (!('a' <= c && c <= 'z') && !('A' <= c && c <= 'Z')) return false;
            if (vowels.contains(c)) judge |= 1;
            else judge |= 1 << 1;
        }
        return judge == 3;
    }


    public void sortColors(int[] nums) {
        // i,j,k
        int i = 0;
        int j = 0;
        int k = 0;
        for (int num : nums) {
            if (num == 0) {
                i++;
            } else if (num == 1) {
                j++;
            } else {
                k++;
            }
        }
        int p = 0;
        while (p < i) {
            nums[p] = 0;
            p++;
        }
        while (p < i + j) {
            nums[p] = 1;
            p++;
        }
        while (p < i + j + k) {
            nums[p] = 2;
            p++;
        }
    }


    public void sortColors2(int[] nums) {
        // p0 cur p2
        int p0 = 0;
        int cur = 0;
        int p2 = nums.length - 1;
        while (p0 < p2) {
            if (nums[cur] == 0) {
                swap(nums, cur, p0);
                cur++;
                p0++;
            } else if (nums[cur] == 2) {
                swap(nums, cur, p2);
                p2--;
            } else {
                cur++;
            }
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public String makeFancyString(String s) {
        char[] chars = s.toCharArray();
        StringBuilder sb = new StringBuilder();
        for (char c : chars) {
            int count = sb.length();
            if (count >= 2 && sb.charAt(count - 1) == c && sb.charAt(count - 2) == c) {
                continue;
            }
            sb.append(c);
        }
        return sb.toString();
    }

    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = 0;
        int j = 0;
        int k = 0;
        int[] res = new int[m + n];
        while (j < m || k < n) {
            if (j == m) {
                res[i++] = nums2[k++];
            } else if (k == n) {
                res[i++] = nums1[j++];
            } else if (nums1[j] < nums2[k]) {
                res[i++] = nums1[j++];
            } else {
                res[i++] = nums2[k++];
            }
        }
        for (i = 0; i < res.length; ++i) {
            nums1[i] = res[i];
        }
    }

    public boolean isPalindrome(int x) {
        String s = String.valueOf(x);
        return new StringBuilder(s).reverse().toString().equals(s);
    }

    // 二分查找
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] == target) {
                return mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }


    public int[] searchRange(int[] nums, int target) {
        if (nums.length == 0) {
            return new int[]{-1, -1};
        }
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        // 检查左边界是否有效（防止越界或元素不匹配）
        if (left >= nums.length || nums[left] != target) {
            return new int[]{-1, -1};
        }
        int l = 0;
        int r = nums.length - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] > target) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return new int[]{left, r};
    }

    public String convert(String s, int numRows) {
        if (numRows < 2) return s;
        List<StringBuilder> rows = new ArrayList<StringBuilder>();
        for (int i = 0; i < numRows; i++) rows.add(new StringBuilder());
        int i = 0, flag = -1;
        for (char c : s.toCharArray()) {
            rows.get(i).append(c);
            if (i == 0 || i == numRows - 1) flag = -flag;
            i += flag;
        }
        StringBuilder res = new StringBuilder();
        for (StringBuilder row : rows) res.append(row);
        return res.toString();
    }


    public String convert2(String s, int numRows) {
        if (numRows < 2) return s;
        List<StringBuilder> rows = new ArrayList<StringBuilder>();
        for (int i = 0; i < numRows; i++) rows.add(new StringBuilder());
        int i = 0, flag = -1;
        for (char c : s.toCharArray()) {
            rows.get(i).append(c);
            if (i == 0 || i == numRows - 1) flag = -flag;
            i += flag;
        }
        StringBuilder sb = new StringBuilder();
        for (StringBuilder row : rows) {
            sb.append(row);
        }
        return sb.toString();
    }

    public int myAtoi(String s) {
        if (s == null) {
            return 0;
        }
        int n = s.length();
        int i = 0;
        int res = 0;
        // 判断是否为负数
        boolean is_negative = false;
        // 跳过空格
        while (i < n && s.charAt(i) == ' ') {
            i++;
        }

        // 如果一样 返回0
        if (i == n) {
            return 0;
        }

        // 处理符号（最多一个）
        if (s.charAt(i) == '+' || s.charAt(i) == '-') {
            if (s.charAt(i) == '-') {
                is_negative = true;
            }
            i++; // 跳过符号位

            // 检查符号后是否仍有符号（如 "+-123"）
            if (i < n && (s.charAt(i) == '+' || s.charAt(i) == '-')) {
                return 0; // 多个符号，非法
            }
        }

        // 符号后必须接数字
        if (i >= n || s.charAt(i) < '0' || s.charAt(i) > '9') {
            return 0; // 无有效数字
        }

        while (i < n && s.charAt(i) >= '0' && s.charAt(i) <= '9') {
            //'0'的 ASCII 码是 48，'1'的是 49，这么一减就从就可以得到真正的整数值
            int tmp = s.charAt(i) - 48;
            //判断是否大于 最大 32 位整数
            if (!is_negative && (res > 214748364 || (res == 214748364 && tmp >= 7))) {
                return 2147483647;
            }
            //判断是否小于 最小 32 位整数
            if (is_negative && (-res < -214748364 || (-res == -214748364 && tmp >= 8))) {
                return -2147483648;
            }
            res = res * 10 + tmp;

            i++;
        }
        return is_negative ? -res : res;
    }


    public boolean isPalindrome4(int x) {
        if (x < 0) {
            return false;
        }
        int ans = 0;
        int old = x;
        while (x > 0) {
            ans = ans * 10 + x % 10;
            x /= 10;
        }
        return ans == old;
    }


    // 二叉树的中序遍历
    public List<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();

        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            res.add(root.val);
            root = root.right;
        }
        return res;
    }

    // 二叉树的前序遍历
    public List<Integer> preorderTraversal(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                res.add(root.val);
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            root = root.right;
        }
        return res;
    }

    // 前序遍历顺序：中-左-右，入栈顺序：中-右-左
    public List<Integer> preorderTraversal2(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if (root == null) {
            return res;
        }
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            res.add(node.val);
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
        return res;
    }


    // 后序遍历 左右根
    public List<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.isEmpty()) {
            if (root != null) {
                stack.push(root);
                res.add(root.val);
                root = root.right;
            } else {
                root = stack.pop();
                root = root.left;
            }
        }
        return res;
    }

    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) {
            return new ArrayList<List<Integer>>();
        }

        List<List<Integer>> res = new ArrayList<>();
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        while (queue.size() > 0) {
            List<Integer> temp = new ArrayList<>();
            for (int i = 0; i < queue.size(); i++) {
                TreeNode node = queue.remove();
                temp.add(node.val);
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            res.add(temp);
        }
        return res;
    }

    // 二叉树的最大深度
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }

    public static List<String> letterCombinations2(String digits) {
        List<String> combinations = new ArrayList<>();  //使用一个集合来存储所有的字母组合结果
        if (digits == null || digits.length() == 0) return combinations;

        //将号码字母对应关系存储进Map
        HashMap<Character, String[]> map = new HashMap<Character, String[]>() {{    //存储为数组更好操作
            put('2', new String[]{"a", "b", "c"});
            put('3', new String[]{"d", "e", "f"});
            put('4', new String[]{"g", "h", "i"});
            put('5', new String[]{"j", "k", "l"});
            put('6', new String[]{"m", "n", "o"});
            put('7', new String[]{"p", "q", "r", "s"});
            put('8', new String[]{"t", "u", "v"});
            put('9', new String[]{"w", "x", "y", "z"});
        }};

        //定义一个队列来存储所有的组合结果
        Queue<String> queue = new LinkedList<>();
        //遍历Digits，取到对应号码对应的字母数组
        for (int i = 0; i < digits.length(); i++) {
            queueLetterCombinations(queue, map.get(digits.charAt(i)));
        }
        //要求返回List
        combinations.addAll(queue);
        return combinations;
    }

    private static Queue<String> queueLetterCombinations(Queue<String> queue, String[] letters) {
        if (queue.isEmpty()) {
            queue.addAll(Arrays.asList(letters));
        } else {
            int len = queue.size();
            for (int i = 0; i < len; i++) {
                String str = queue.poll();
                for (String letter : letters) {
                    queue.add(str + letter);
                }
            }
        }
        return queue;
    }

    public int canBeTypedWords(String text, String brokenLetters) {
        HashSet<Character> broken = new HashSet<>();
        for (char c : brokenLetters.toCharArray()) {
            broken.add(c);
        }
        int res = 0;
        boolean flag = true;
        for (char c : text.toCharArray()) {
            if (c == ' ') {
                if (flag) {
                    res++;
                }
                flag = true;
            } else if (broken.contains(c)) {
                flag = false;
            }
        }
        if (flag) {
            res++;
        }
        return res;
    }


}
